package com.chen.demo.javase.algorithm.leetcode.editor.cn;
//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 
//
// 示例 1： 
//
// 输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
// 
//
// 示例 2： 
//
// 输入: "cbbd"
//输出: "bb"
//
// Related Topics 字符串 动态规划
// 👍 3064 👎 0

import com.sun.deploy.util.StringUtils;

public class LongestPalindromicSubstring {


    public static void main(String[] args) {
        System.out.println("babad回文串:" + solution("babad"));
        System.out.println("cbbd回文串:" + solution("cbbd"));
        System.out.println("ac回文串:" + solution("ac"));
        System.out.println("a回文串:" + solution("a"));
    }

    public static String solution(String str) {
        int len = str.length();
        boolean[][] dp = new boolean[len][len];
        int start = 0;
        int maxLen = 1;
        if (str.length() <= 1) {
            return str;
        }
        for (int i = 0; i < len; i++) {
            // 对角线
            dp[i][i] = true;
        }
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                // 首尾相等，才有有后面判断逻辑
                if (str.charAt(i) == str.charAt(j)) {
                    if (i == 0) {
                        if (j <= 1) {
                            dp[i][j] = true;
                        } else {
                            dp[i][j] = dp[i + 1][j - 1];
                        }
                    } else {
                        if (j - i <= 2) {
                            // j与i之间的必须有2个元素
                            // j-i-1 > 2 => j-i>2
                            dp[i][j] = true;
                        } else {
                            dp[i][j] = dp[i + 1][j - 1];
                        }
                    }
                } else {
                    dp[i][j] = false;
                }
                if (dp[i][j] && j - i + 1 > maxLen) {
                    start = i;
                    maxLen = j - i + 1;
                }
            }
        }

        return str.substring(start, start + maxLen);
    }

//leetcode submit region end(Prohibit modification and deletion)

}